package leetcode_100;

import helpclass.ListNode;

/**
 *@author 周杨
 *MergeTwoSortedLists_21 合并两个有序链表
 *describe:用递归 
 *2018年12月22日 下午4:16:45
 */
public class MergeTwoSortedLists_21 {
	 /**
	 * describe:用递归 最优解
	 * 2018年12月22日 下午4:15:32
	 */
	public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
	        if (l1==null)
	            return l2;
	        if (l2==null)
	            return  l1;
	        
	        ListNode result=null;
	        
	        if (l1.val <= l2.val) {
	            result=new ListNode(l1.val);
	            result.next=mergeTwoLists(l1.next,l2);
	        }   
	        else if (l1.val > l2.val){
	            result=new ListNode(l2.val);
	            result.next=mergeTwoLists(l2.next,l1);            
	        }
	        return result;
	    }
	
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode head,now;
        if(l1.val<l2.val) {
        	head=new ListNode(l1.val);
        	l1=l1.next;
        }
        else {
        	head=new ListNode(l2.val);
        	l2=l2.next;
        }
        ListNode run=head;
        while(l1!=null&&l2!=null) {
        	if(l1.val<l2.val) {
            	now=new ListNode(l1.val);
            	l1=l1.next;
            	run.next=now;
            	run=now;
            }
            else {
            	now=new ListNode(l2.val);
            	l2=l2.next;
            	run.next=now;
            	run=now;
            }
        }
        while(l1!=null) {
        	now=new ListNode(l1.val);
        	l1=l1.next;
        	run.next=now;
        	run=now;
        }
        while(l2!=null) {
        	now=new ListNode(l2.val);
        	l2=l2.next;
        	run.next=now;
        	run=now;
        }
        return head;
    }
}
